// @algorithm @lc id=100291 lang=cpp
// @title diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
    // @test([1,2,3,4])=[1,3,2,4]
    // @test([1,2,3,4])=[1,3,2,4]
public:
    vector<int> exchange(vector<int> &nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left < right) {
            if (isOdd(nums[left]) && isEven(nums[right])) {
                ++left;
                --right;
            }
            else if (isEven(nums[left]) && isOdd(nums[right])) {
                swap(nums[left], nums[right]);
                ++left;
                --right;
            }
            else if (isEven(nums[left]) && isEven(nums[right])) {
                --right;
            }
            else {
                ++left;
            }
        }
        return nums;
    }

    bool isOdd(int n) {
        return n % 2 != 0;
    }

    bool isEven(int n) {
        return n % 2 == 0;
    }
};